package algorithme;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Foret {
	
	private int[] parent;
	private int[] profondeur;
	private int[] arbre;
	private Map<Integer, Set<Arete>> aretesAdjacentes;
	private Set<Integer> sommetsRestant;

	public Foret(Map<Integer, Set<Arete>> aretesAdjacentes){
		this.aretesAdjacentes = aretesAdjacentes;
		int nbSommetMax=0;
		for(int sommetId : aretesAdjacentes.keySet())
			nbSommetMax = (sommetId>nbSommetMax)?sommetId:nbSommetMax;
		nbSommetMax++;
		parent = new int[nbSommetMax];
		profondeur = new int[nbSommetMax];
		arbre = new int[nbSommetMax];
		Arrays.fill(arbre, -1);
		Arrays.fill(profondeur, -1);
		Arrays.fill(parent, -1);
		sommetsRestant = new HashSet<Integer>(aretesAdjacentes.keySet());
		generationForet();
	}
	
	public Foret(Graphe graphe){
		this(graphe.getAretesAdjacentes2());
	}
	
	protected void generationForet(){
		int arbre = 0;
		while(sommetsRestant.size()!=0){
			int racine = sommetsRestant.iterator().next();
			this.parent[racine]=racine;
			generationArbre(0,racine, arbre++);
		}
	}
	
	protected void generationArbre (int profondeur, int parent, int arbreID){
		this.profondeur[parent]=profondeur;
		this.arbre[parent]=arbreID;
		sommetsRestant.remove(parent);
		for(Arete arete :aretesAdjacentes.get(parent)){
			int autreSommet = (arete.getU()==parent)?arete.getV():arete.getU();
			if( sommetsRestant.contains(autreSommet)){
				this.parent[autreSommet]=parent;
				generationArbre(profondeur+1,autreSommet,arbreID);
			}
		}
	}
	
	public int ancetreCommun(int i, int j){
		return ancetreCommun(i, j, 0);
	}
	
	private int ancetreCommun(int i, int j, int longueur){
		if(profondeur[i]>profondeur[j])
			return ancetreCommun(parent[i], j, getArete(i, parent[i]).getPoids());
		else if(profondeur[i]<profondeur[j])
			return ancetreCommun(i,parent[j], getArete(j, parent[j]).getPoids());
		else{
			if(i==j)
				return i;
			else
				return ancetreCommun(parent[i], parent[j], getArete(i, parent[i]).getPoids()+getArete(j, parent[j]).getPoids());
		}
	}
	
	public int arbre(int sommet){
		return arbre[sommet];
	}
	
	public boolean contient(Arete arete){
		if(aretesAdjacentes.containsKey(arete.getU()))
			return aretesAdjacentes.get(arete.getU()).contains(arete);
		return false;
	}
	
	public Arete getArete(int i, int j){
		for(Arete arete : aretesAdjacentes.get(i)){
			if((arete.getU() == i && arete.getV()==j) || (arete.getU() == j && arete.getV()==i)){
				return arete;
			}
		}
		return null;
	}
	
	public int nbSommets(){
		return aretesAdjacentes.keySet().size();
	}
}